#include <vector>
#include <pthread.h>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <cmath>
#include <semaphore.h>
#include <unordered_map>
#include <cstdlib>
#include <sys/time.h>

#define TIME_IN_MS(x) ((x.tv_sec * 1000) + (x.tv_usec / 1000.0))

using namespace std;

int num_threads;
vector<string> file_list = { "1_130_22_8", "2_254_106_53", "3_562_170_53", "4_1011_539_263", "5_2362_1226_453", "6_3799_2759_1953", "7_8399_6375_4535" };
vector<string> method_paths = { "method1_result", "method2_result" };

int total_cols, total_rows, cols, rows1, rows2;
int** matrix = nullptr;
int* leading_positions = nullptr;
unordered_map<int, int> lp_to_row;

pthread_barrier_t bar1, bar2, bar3, bar4;

void release_memory() {
    if (matrix) {
        for (int i = 0; i < total_rows; i++)
            delete[] matrix[i];
        delete[] matrix;
        delete[] leading_positions;
        matrix = nullptr;
        leading_positions = nullptr;
    }
}

void initialize_matrix() {
    matrix = new int* [total_rows];
    for (int i = 0; i < total_rows; i++) {
        matrix[i] = new int[total_cols]();
    }
    leading_positions = new int[total_rows]();
    fill_n(leading_positions, total_rows, -1);
    lp_to_row.clear();
}

void parse_file_name(const string& file_name) {
    stringstream ss(file_name);
    ss >> cols >> cols >> rows1 >> rows2;
    total_cols = cols / 32 + (cols % 32 != 0 ? 1 : 0);
    total_rows = rows1 + rows2;
}

void load_file(const string& file_path, int& row) {
    ifstream input(file_path);
    string line;
    while (getline(input, line)) {
        stringstream ss(line);
        int pos;
        while (ss >> pos) {
            matrix[row][pos / 32] |= (1 << (pos % 32));
            leading_positions[row] = max(pos, leading_positions[row]);
        }
        if (row >= rows2) {
            if (lp_to_row.count(leading_positions[row])) {
                cerr << "Conflict in leading positions at rows: " << lp_to_row[leading_positions[row]] << " and " << row - rows2 << endl;
                exit(EXIT_FAILURE);
            }
            lp_to_row[leading_positions[row]] = row;
        }
        row++;
    }
}

void load_data(const string& file_name) {
    int current_row = 0;
    load_file("/pthread/test/" + file_name + "/2.txt", current_row);
    load_file("/pthread/test/" + file_name + "/1.txt", current_row);
}

void reset_matrix() {
    for (int i = 0; i < total_rows; i++) {
        fill_n(matrix[i], total_cols, 0);
    }
    fill_n(leading_positions, total_rows, -1);
    lp_to_row.clear();
    load_data(file_list[num_threads]);
}

void sequential_gaussian_elimination() {
    for (int i = 0; i < rows2; i++) {
        while (leading_positions[i] > -1) {
            if (lp_to_row.count(leading_positions[i])) {
                int row = lp_to_row[leading_positions[i]];
                bool lp_changed = false;
                for (int j = 0; j < total_cols; j++) {
                    matrix[i][j] ^= matrix[row][j];
                }
                for (int j = total_cols - 1; j >= 3; j -= 4) {
                    int combined = matrix[i][j] | matrix[i][j - 1] | matrix[i][j - 2] | matrix[i][j - 3];
                    if (combined == 0) continue;
                    break;
                }
                for (int j = total_cols - 1; j >= 0; j--) {
                    if (matrix[i][j] != 0) {
                        lp_changed = true;
                        for (int k = 31; k >= 0; k--) {
                            if (matrix[i][j] & (1 << k)) {
                                leading_positions[i] = j * 32 + k;
                                break;
                            }
                        }
                        break;
                    }
                }
                if (!lp_changed)
                    leading_positions[i] = -1;
            } else {
                lp_to_row[leading_positions[i]] = i;
                break;
            }
        }
    }
}

void* parallel_gaussian_elimination(void* param) {
    long long tid = (long long)param;
    for (int i = 0; i < rows2; i++) {
        while (leading_positions[i] > -1) {
            if (lp_to_row.count(leading_positions[i])) {
                int row = lp_to_row[leading_positions[i]];
                for (int j = tid; j < total_cols; j += num_threads) {
                    matrix[i][j] ^= matrix[row][j];
                }
                pthread_barrier_wait(&bar1);
                if (tid == 0) {
                    bool lp_changed = false;
                    for (int j = total_cols - 1; j >= 3; j -= 4) {
                        int combined = matrix[i][j] | matrix[i][j - 1] | matrix[i][j - 2] | matrix[i][j - 3];
                        if (combined == 0) continue;
                        break;
                    }
                    for (int j = total_cols - 1; j >= 0; j--) {
                        if (matrix[i][j] != 0) {
                            lp_changed = true;
                            for (int k = 31; k >= 0; k--) {
                                if (matrix[i][j] & (1 << k)) {
                                    leading_positions[i] = j * 32 + k;
                                    break;
                                }
                            }
                            break;
                        }
                    }
                    if (!lp_changed)
                        leading_positions[i] = -1;
                }
                pthread_barrier_wait(&bar2);
            } else {
                pthread_barrier_wait(&bar4);
                if (tid == 0) {
                    lp_to_row[leading_positions[i]] = i;
                }
                pthread_barrier_wait(&bar3);
                break;
            }
        }
    }
    return nullptr;
}

void run_parallel_gaussian_elimination() {
    pthread_barrier_init(&bar1, nullptr, num_threads);
    pthread_barrier_init(&bar2, nullptr, num_threads);
    pthread_barrier_init(&bar3, nullptr, num_threads);
    pthread_barrier_init(&bar4, nullptr, num_threads);
    pthread_t* threads = new pthread_t[num_threads];
    for (int i = 0; i < num_threads; i++)
        pthread_create(&threads[i], nullptr, parallel_gaussian_elimination, (void*)(long long)i);
    for (int i = 0; i < num_threads; i++)
        pthread_join(threads[i], nullptr);
    delete[] threads;
    pthread_barrier_destroy(&bar1);
    pthread_barrier_destroy(&bar2);
    pthread_barrier_destroy(&bar3);
    pthread_barrier_destroy(&bar4);
}

void output_results() {
    for (int i = 0; i < rows2; i++) {
        if (leading_positions[i] == -1) {
            cout << endl;
            continue;
        }
        for (int j = total_cols - 1; j >= 0; j--) {
            for (int k = 31; k >= 0; k--) {
                if (matrix[i][j] & (1 << k)) {
                    cout << j * 32 + k << " ";
                }
            }
        }
        cout << endl;
    }
}

void verify_results(const string& file_name) {
    ifstream expected_result("/pthread/test/" + file_name + "/3.txt");
    string line;
    for (int i = 0; i < rows2; i++) {
        getline(expected_result, line);
        if (leading_positions[i] == -1) {
            if (line.length() > 1) {
                cerr << "Error in results" << endl;
                exit(EXIT_FAILURE);
            }
            continue;
        }
        stringstream ss(line);
        int pos;
        for (int j = total_cols - 1; j >= 0; j--) {
            for (int k = 31; k >= 0; k--) {
                if (matrix[i][j] & (1 << k)) {
                    ss >> pos;
                    if (pos != j * 32 + k) {
                        cerr << "Error in results" << endl;
                        exit(EXIT_FAILURE);
                    }
                }
            }
        }
    }
    cout << "Validation successful" << endl;
    expected_result.close();
}

void test_function(void (*func)()) {
    int iteration_count = 0;
    timeval start_time, iteration_start, iteration_end, current_time;
    float total_time = 0;
    gettimeofday(&start_time, nullptr);
    gettimeofday(&current_time, nullptr);
    while (TIME_IN_MS(current_time) - TIME_IN_MS(start_time) < 100) {
        iteration_count++;
        reset_matrix();
        gettimeofday(&iteration_start, nullptr);
        func();
        gettimeofday(&iteration_end, nullptr);
        total_time += (TIME_IN_MS(iteration_end) - TIME_IN_MS(iteration_start));
        gettimeofday(&current_time, nullptr);
    }
    verify_results(file_list[num_threads]);
    float avg_time = total_time / iteration_count;
    cout << file_list[num_threads] << " " << method_paths[num_threads] << " " << iteration_count << " " << avg_time << endl;
    ofstream result_file(method_paths[num_threads], ios::app);
    result_file << avg_time << ' ';
    result_file.close();
}

int main(int argc, char* argv[]) {
    num_threads = atoi(argv[1]);
    void (*functions[2])() = { sequential_gaussian_elimination, run_parallel_gaussian_elimination };
    for (const auto& file_name : file_list) {
        parse_file_name(file_name);
        initialize_matrix();
        for (int i = 0; i < 2; i++) {
            method_paths[num_threads] = method_paths[i] + to_string(num_threads);
            test_function(functions[i]);
        }
        release_memory();
    }
    return 0;
}
